/*
 * @lc app=leetcode.cn id=493 lang=javascript
 *
 * [493] 翻转对
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var reversePairs = function (nums) {
  if (nums.length === 0) {
    return 0;
  }
  return sort(nums, 0, nums.length - 1);

  function sort(nums, left, right) {
    if (left >= right) {
      return 0;
    }
    const mid = ((right - left) >> 1) + left;
    const n1 = sort(nums, left, mid);
    const n2 = sort(nums, mid + 1, right);

    return n1 + n2 + merge(nums, left, mid, right);
  }

  function merge(nums, left, mid, right) {
    // 计算翻转对
    let i = left;
    let j = mid + 1;
    let result = 0;

    while (i <= mid && j <= right) {
      if (nums[i] > nums[j] * 2) {
        result += mid - i + 1;
        j++;
      } else {
        i++;
      }
    }

    // 排序
    const temp = new Array(right - left + 1);
    let idx = 0;
    i = left;
    j = mid + 1;
    while (i <= mid && j <= right) {
      if (nums[i] < nums[j]) {
        temp[idx++] = nums[i++];
      } else {
        temp[idx++] = nums[j++];
      }
    }
    while (i <= mid) {
      temp[idx++] = nums[i++];
    }
    while (j <= right) {
      temp[idx++] = nums[j++];
    }

    for (let k = 0; k < temp.length; k++) {
      nums[left + k] = temp[k];
    }
    return result;
  }
};
// @lc code=end
